搭积木
题目 搭积木
思路分析
题目意思看懂了 但是不怎么好下手
数据范围挺小的 100
暴搜把所有情况弄出来判断合法与否估计能拿些分（类似于八皇后问题的按点枚举的写法）
有点巧妙
- mem[num][left][right] 数组用来存储从第 num 层积木放置，从位置 left 到 right 的所有可能的方案数。这样可以避免重复计算相同状态，实现记忆化。
- arr[i][j] 存储每一层积木放置的喜好。
dfs(num, left, right):
- 当 num == 0 时，表示没有更多层可以放置积木，返回 0。
- 对于任意 num != 0，遍历当前层 num 从位置 left 到 right：
- 如果位置 i 是 '.'（可以放置积木），则从这个位置开始尝试放置积木，直到遇到 'X' 或到达 right。
- 对于每个有效的连续段 [i, j]，计算在下一层 num-1 上同样的段 [i, j] 可能的放置方案数，并将其加到总和中。
- 结果中包含一个加一的操作，这表示在当前层 [left, right] 区间内至少放置一个积木的方案数。
代码实现
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
#define N 105
const ll mor=7+1e9;
char arr[N][N];
ll mem[N][N][N];
int n, m;
ll dfs(int num, int left, int right) {
if (mem[num][left][right]!=-1) return mem[num][left][right];
if (num == 0) mem[num][left][right] = 0;
else if (num != 0) {
ll sum = 0;
for (int i = left; i <= right; i++) {
if (arr[num][i] == '.') {
for (int j = i; j <= right; j++) {
if (arr[num][j] != 'X') {
sum += dfs(num - 1, i, j) + 1;
}
else break;
}
}
}
mem[num][left][right] = sum%mor;
}
return mem[num][left][right];
}
int main()
{
// 请在此输入您的代码
memset(mem, -1, sizeof mem);
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%s", &arr[i][1]);
}
cout << (dfs(n, 1, m) + 1)%mor;
return 0;
}
💬 评论